package com.hackerank.warmup;

/**
 * Jumping on the clouds 在云上跳
 *  https://www.hackerrank.com/challenges/jumping-on-the-clouds/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup
 * 题目大意：
 * 1、输入第一个数 n，代表有多少云朵
 * 2、接下来输入n个数的数组，数组的值是0或1，0代表可以踩的云，1代表不能踩的云，必须跳过去
 * 3、数组的开头和结尾都是0
 * 4、一次可以跳1步远或2步远，如000，可以从第一个0跳到第二个0代表一步远，也可以从第一个0跳到第三个0代表2步远。010则必须跳2步远
 * 5、输出从第一个0跳到最后一个0，一共跳几次（次数，不是几步远）
 *
 * 解题思路：
 * 1、遍历数组中的值，遇到0则计数+1
 * 2、遇到1，则需要跳过步数为 当前1前面的0的总数除以2 加 1（跳过1）
 * 3、将计数清零继续遍历
 * 4、当遍历到最后一个0后，需要单独加上 0的个数 除以2
 *
 * 时间复杂度O(n)，空间复杂度O(1)
 * **/
public class JumpingOnTheClouds {
    static int jumpingOnClouds(int[] c) {
        int step = 0;
        int count = 0;
        for(int i=0;i<c.length;i++){
            if(c[i] == 0){
                count ++;
            }else{
                step += (count/2 + 1);
                count = 0;
            }
        }
        step += count/2;
        return step;
    }
}
